package 蓝桥._2024.砍柴;

import java.sql.Timestamp;
import java.util.*;

public class Main3 {
    // 素数表: 也是合法操作表
    static List<Integer> primeList = new ArrayList<>();
    // 先手必败
    static List<Integer> failList = new ArrayList<>();

    static void init(){
        int max = 100010;
        boolean[] isPrime = new boolean[max];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        // 素数筛：如果i是素数，那么i的倍数都不是素数
        for(int i = 2;i < max;i++ ){
            if(isPrime[i]){
                for(int j= 2 * i;j<max;j+=i){
                    isPrime[j] = false;
                }
            }
        }
        for (int i = 0; i < max; i++) {
            if(isPrime[i])
                primeList.add(i);
        }
        // 先手必败
        failList.add(0);
        failList.add(1);
        System.out.print("0,1");

        for(int i=2;i<max;i++){
            // 如果一个数，所有的合法操作都不能让其变为下一次为先手必败的状态，则其为先手必败状态
            boolean isFail = true;
            for(int j = 0; j< primeList.size();j++){
                if(i < primeList.get(j))
                    break;
                if( Collections.binarySearch(failList, i - primeList.get(j)) >= 0){
                    isFail = false;
                    break;
                }
            }
            if(isFail) {
                failList.add(i);
                System.out.printf(",%d",i);
            }
        }

    }

    public static void main(String[] args) {

        init();



        Scanner scan = new Scanner(System.in);
        int T = scan.nextInt();
        int[] lens = new int[T];
        for (int i = 0; i < T; i++) {
            lens[i] = scan.nextInt();
        }

        for(int i=0;i < T;i++){
            if(Collections.binarySearch(failList,lens[i])>=0)
                System.out.println("0");
            else
                System.out.println("1");
        }

        scan.close();



    }
}
